1. Field
The present system is related to the compression of integer data.
2. Description of the Related Art
As the Internet's popularity grows, more businesses are establishing a presence on the Internet. These businesses typically set up web sites that run one or more web applications. One disadvantage of doing business on the Internet is that if the web site goes down, becomes unresponsive or otherwise is not properly serving customers, the business is losing potential sales and/or customers. Similar issues exist with Intranets and Extranets. Thus, service oriented architecture (SOA) application management solutions have been developed which proactively detect and diagnose performance problems for web applications and web sites to ensure that they run properly. One such application management system is Introscope® by CA, Inc., Wily Technology Division, South San Francisco, Calif.
Applications such as Introscope® acquire and store a tremendous amount of data for their operation, and rely on data compression techniques to minimize storage space and transmission bandwidth. In general, data compression schemes involve an encoding engine which encodes data prior to storage or transmission, and a decoding engine which is capable of performing the reverse operation to decode the data upon receipt or retrieval from storage. One type of compression technique is a lossy data compression, where high compression rates are achieved, but at the sacrifice of some resolution of the original encoded data upon decoding. Lossy data compression techniques are often used to transmit multi-media data requiring high bandwidth transfer rates and where loss of some fidelity in the data will not be perceptible in the decoded media.
Other situations require lossless data compression where the decoded data is a full reconstruction of the encoded data. One well known technique for lossless compression of positive integers is called the Elias Delta coding algorithm, developed by M.I.T. professor Peter Elias in the 1970's. The conventional Elias Delta scheme for coding a natural number xε={1, 2, 3, . . . } will now be explained with reference to the prior art flowchart of FIG. 1 and a specific arbitrary example showing the Elias Delta coding of the integer value x=13. In step 40 the integer data value is received in binary format:13base 10=1101base 2 In step 44, the number of digits, N, in the binary value of step 42 is determined.1101 has N=4 digitsN may be determined mathematically by noting N−1 is the highest whole number power of 2 contained in the original integer value x. Stated another way, N−1=the largest integer contained in Log2 x. This is commonly written N−1=Log2 x, and is referred to with this notation herein.N−1=Log2 13→N−1=3; N=4.Another way of describing N is that N is the number of digits in the binary representation of x, and N−1 is the number of digits in the binary representation of x with the most significant bit (MSB) removed.
In step 46, N is converted to a binary number:4base 10=100base 2 And in step 48, the number of digits, N′, in the binary conversion of N is determined.100 has N′=3 digits; N′−1=2.Again, N′ may be determined mathematically by noting N′−1 is the highest whole number power of 2 contained in N.N′−1=Log2 4→N′−1=2, N′=3.
The Elias Delta code Eδ(x) for the original integer x is then obtained from three sub parts:
Eδ(x)1=N′−1 number of zeros (step 48);
Eδ(x)2=binary representation of N (step 42); and
Eδ(x)3=The remaining N−1 digits of the binary representation of x (i.e., the binary representation of x with the MSB removed).
Thus, Eδ(13)=Eδ(13)1=00Eδ(13)2=100Eδ(13)3=101=101Eδ(13)=00100101.The prior art in FIG. 2 shows the Elias Delta code values for the integers 0 through 16 as well as larger numbers 32, 64 and 128.
Once the Elias Delta code value for an integer is obtained, it may be output in step 50. The output may be from a processor to a persistent storage media, or the output may be from the processor to a communications interface for transmission to another computing device. The Elias Delta code value for an integer may be stored on a persistent storage media or transmitted via a network connection as a single value. Alternatively, as shown in prior art FIG. 3, it may be transmitted in its sub-components Eδ(x)1, Eδ(x)2 and Eδ(x)3. Namely, Eδ(x)1 may be transmitted or stored in a FIFO data structure in a step 52. Eδ(x)2 may be transmitted or stored in a FIFO data structure in a step 54. And Eδ(x)3 may be transmitted or stored in a FIFO data structure in a step 56. The sub-components are transferred and stored in the above order so that when they are received or retrieved from the FIFO data structure, the subcomponents needed to decode other subcomponents of the Elias Delta code are examined in the proper order. In order to reconstruct the original integer value from the Elias Delta code value, the reverse operations may be performed on the Elias Delta code values.
One problem with the Elias Delta coding scheme is that it must work for any input integer value and it must therefore reserve code space for any value. As can be seen for example in FIG. 2, for large input values such as x=64, the Eδ(64) takes up more storage space and/or transmission bandwidth than the native binary value itself (Eδ(64)=00111000000 as compared to 1000000 for the binary value). However, in many real world applications, the input integer value is bounded. For example, a register may have a given size, e.g., 4 bits. As another example, many classes of data have a size set by industry standard, e.g., transmission of color values in multi-media stream range between 0 and 255 and they are contained within 8 bits. Elias Delta coding does not take advantage of this knowledge that data systems are often bounded so that input values range over a gamut having a known minimum and a known maximum.